package leetcode.code322;

import java.util.Arrays;

/**
 * 超时
 *
 * @author CaoYu
 * @date 2021年9月14日
 * @description
 */
public class Solution extends Solution322 {

	@Override
	public int coinChange(int[] coins, int amount) {
		Arrays.sort(coins);
		int coinsNum = this.howMany(coins, amount);
		return coinsNum;
	}

	private int howMany(int[] coins, int rest) {
		System.out.println(rest);
		if (rest == 0)
			return 0;
		int r = this.less(coins, rest);
		int res = -1;
		while (r >= 0) {
			int num = rest / coins[r];
			while (num > 0) {
				int left = rest - num * coins[r];
				res = howMany(coins, left);
				if (res != -1) {
					return res + num;
				}
				num--;
			}
			r--;
		}
		return res;
	}

	public int less(int[] coins, int amount) {
		int l = 0;
		int r = coins.length - 1;
		int ans = -1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (coins[m] == amount) {
				return m;
			} else if (coins[m] > amount) {
				r = m - 1;
			} else {
				ans = m;
				l = m + 1;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
//		so.debug5();
//		so.debug6();
		so.debug7();
	}

}
